8735. Train swapping

At an old railway station, you may still encounter one of the last remaining “train swappers”. A train swapper is an employee of the railroad, whose sole job it is to rearrange the carriages of trains. Once the carriages are arranged in the optimal order, all the train driver has to do, is drop the carriages off, one by one, at the stations for which the load is meant.

The title “train swapper” stems from the first person who performed this task, at a station close to a railway bridge. Instead of opening up vertically, the bridge rotated around a pillar in the center of the river. After rotating the bridge 90 degrees, boats could pass left or right.

The first train swapper had discovered that the bridge could be operated with at most two carriages on it. By rotating the bridge 180 degrees, the carriages switched place, allowing him to rearrange the carriages (as a side effect, the carriages then faced the opposite direction, but train carriages can move either way, so who cares).

Now that almost all train swappers have died out, the railway company would like to automate their operation. Part of the program to be developed, is a routine which decides for a given train the least number of swaps of two adjacent carriages necessary to order the train. Your assignment is to create that routine.

Input. First line contains the number of test cases n. Each test case consists of two lines. The first line of a test case contains an integer l (0 ≤ l ≤ 10000), determining the length of the train. The second line of a test case contains a permutation of the numbers 1 through l, indicating the current order of the carriages. The carriages should be ordered such that carriage 1 comes first, then 2, etc. with carriage l coming last.

Output. For each test case output the sentence: "Optimal train swapping takes s swaps.", where s is an integer.

Sample input	Sample output
3 3 1 3 2 4 4 3 2 1 2 2 1	Optimal train swapping takes 1 swaps. Optimal train swapping takes 6 swaps. Optimal train swapping takes 1 swaps.

SOLUTION

inversions

Algorithm analysis

Let the array m contains the input permutation – the current order of the carriages. The required minimum number of permutations equals to the number of inversions in the permutation.

An inversion is a pair of numbers (m_i, m_j) such that i < j but m_i > m_j. That is, a pair of numbers forms an inverse if they are not in the correct order.

For example, the array m = {3, 1, 2} has two inversions: (3, 1) and (3, 2). The pair (1, 2) does not form an inversion, since the numbers 1 and 2 stand in the correct order relative to each other.

The number of inversions in the array of length n can be calculated using a double loop: we iterate over all possible pairs (i, j) for which 1 ≤ i < j ≤ n, and if m_i > m_j, then we have an inversion.

Example

Consider an example of counting inversions in a permutation. Under each number we write down the number of inversions that it forms with the elements to the right of it. Let inv[i] contains the number of j such that i < j and m[i] > m[j].

The total number of inversions is 16.

Exercise

Simulate the solution for the next sample.

Algorithm realization

Declare the array m.

int m[100010];

Sequentially, process the test for the problem.

scanf("%d", &tests);

while (tests--)

{

Read the input order of the carriages into the array m.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

The minimum number of permutations for putting the train in order is calculated in the variable res.

res = 0;

for (i = 0; i < n - 1; i++)

for (j = i + 1; j < n; j++)

if (m[i] > m[j]) res++;

Print the answer.

printf("Optimal train swapping takes %lld swaps.\n", res);

}